package leetcode.code2029;

public class Solution7 {

	boolean Alice = true;
	boolean Bob = false;

	public boolean stoneGameIX(int[] stones) {
		int mod0 = 0, mod1 = 0, mod2 = 0;
		for (int num : stones) {
			int mod = num % 3;
			if (mod == 0) {
				mod0++;
			} else if (mod == 1) {
				mod1++;
			} else {
				mod2++;
			}
		}
		mod0 = (mod0 & 1) == 1 ? 1 : 0;
		// 11212 12121
		// 221212 1212
		if (mod1 > mod2) {
			int more = 0;
			if (mod2 > 3) {
				more = mod2 - 3;
				mod2 -= more;
				mod1 -= more;
			}
			mod1 = Math.min(mod1, 6);
		} else {
			int more = 0;
			if (mod1 > 3) {
				more = mod1 - 3;
				mod2 -= more;
				mod1 -= more;
			}
			mod2 = Math.min(mod2, 6);
		}
		Boolean[][][][] hash = new Boolean[2][mod0 + 1][mod1 + 1][mod2 + 1];
		return this.stoneGameIX(Alice, hash, mod0, mod1, mod2, 0);
	}

	private boolean stoneGameIX(boolean who, Boolean[][][][] hash, int mod0, int mod1, int mod2, int total) {
		if (mod0 == 0 && mod1 == 0 && mod2 == 0) {
			return this.Bob;
		}
		int index = who ? 0 : 1;
		if (hash[index][mod0][mod1][mod2] != null) {
			return hash[index][mod0][mod1][mod2];
		}
		if (mod0 > 0 && total % 3 != 0) {// if(有的选 && 选了还对){ 就试一试 }
			if (this.stoneGameIX(!who, hash, mod0 - 1, mod1, mod2, total) == who) {// 一试还是我赢了
				hash[index][mod0][mod1][mod2] = who;
				return who;// 那就选这个
			}
		}
		if (mod1 > 0 && (total + 1) % 3 != 0) {// 0不行就试一试1
			if (this.stoneGameIX(!who, hash, mod0, mod1 - 1, mod2, total + 1) == who) {
				hash[index][mod0][mod1][mod2] = who;
				return who;
			}
		}
		if (mod2 > 0 && (total + 2) % 3 != 0) {// 0，1都不行就试一试2
			if (this.stoneGameIX(!who, hash, mod0, mod1, mod2 - 1, total + 2) == who) {
				hash[index][mod0][mod1][mod2] = who;
				return who;
			}
		}
		hash[index][mod0][mod1][mod2] = !who;
		return !who;// 干了， 我输了
	}



}
